The ability to detect and correct errors is an important feature of data transmission and data storage systems. Transmitted or stored data is often susceptible to noise or distortion that can cause bits to “flip”, corrupting the integrity of the data. A common technique for error detection and correction involves adding additional bits known as “parity bits” to a data word. The parity bits are calculated in such a way that they reflect characteristics of the data word. For example, in one conventional technique, each parity bit is associated with a different subset of bits in the data word. The parity bit is set to 1 if an odd number of bits in the associated subset are set to 1. The parity bit is set to 0 if an even number of bits in the associated subset are set to 1. Thus, any parity bit together with its associated subset of bits will contain an even number of 1s. The parity bits are then encoded together with the data word. At a later time (e.g., after transmission of an encoded data word), a similar parity calculation is executed to determine if the parity bits are still correct (i.e. if a parity bit together with its associated subset of bits still contains an even number of 1s). If a bit changes during transmission of the data word, one or more parity bits will be incorrect (i.e. the parity bit together with its associated subset of bits contains an odd number of 1s). This indicates an error in the data word.
An example of a common error detection/correction code is a SECDED (Single Error Correction Double Error Detection) Hamming code. As is known in the art, a SECDED Hamming code computes parity bits in such a way that a change to any single bit produces a unique “error code” derived from the parity calculation. By examining which parity bits are incorrect, the single bit in error can be identified and can therefore be corrected. Furthermore, the parity bits are calculated in such a way that a two bit error (or other even numbered bit error) can be detected. However, two bit errors are not correctable.
The conventional SECDED Hamming code is not able to detect three bit errors. Rather, in the presence of a three bit error, a conventional SECDED code returns an error code that is indistinguishable from an error code resulting from a single bit error. Therefore, in the presence of a three bit error, a conventional Error Correction Code (ECC) circuit will erroneously “correct” a bit that may actually be valid. This further corrupts the integrity of the data. Therefore, what is needed is an ECC module that can distinguish between three bit errors and single bit errors.